import java.util.Arrays;

public class HashBucket {
    //模拟实现hashMap
    // 数组+链表

    //hashMap，有键值对
    static class Node{
        private int key;
        private int value;
        private Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //负载因子比较值
    public static final double DEFAULT_LOAD_FACTOR=0.75f;

    //数组 存放结点
    public Node[]arr;
    //记录哈希桶内有效元素个数
    public int undersize;

    //创建hashBucket时初始化
    public HashBucket() {
        //默认创建10个元素数组
        this.arr=new Node[10];
        this.undersize=0;
    }



    //哈希函数
    private int hash(int key,int len){
        return key%len;
    }

    //扩容
    private void capacity(Node[]arr){
        Node[]newArray=new Node[arr.length*2];
        //遍历当前数组
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while (cur != null) {
                //记录cur的下一个
                Node curNext=cur.next;
                //计算cur在newArray新的位置
                int index=hash(cur.key,newArray.length);
                //头插法插入newArray
                cur.next=newArray[index];
                newArray[index]=cur;
                //继续往后走
                cur = curNext;
            }
        }
        this.arr=newArray;
    }
    //设置 key 对应的 value
    /*
    如果key值不存在,则返回值是null,
    但是key值如果存在,则会返回原先被替换掉的value值
     */
    public int put(int key, int value) {
        //负载因子大于0.75扩容
        if (undersize / arr.length > DEFAULT_LOAD_FACTOR) {
            capacity(this.arr);
        }

        //哈希函数
        int index = hash(key, arr.length);
        //遍历该位置查看是否有key
        Node cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                //该链表有key,修改value
                int oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
            cur = cur.next;
        }
        //没有key，创建节点
        Node node = new Node(key, value);
        //头插法
        node.next = arr[index];
        arr[index] = node;
        undersize++;
        return -1;
    }






    //返回 key 对应的 value
    /*
    该方法返回指定键所映射的值。
    如果此映射不包含该键的映射关系，则返回null
     */
    int get(int key){
        //哈希函数
        int index=hash(key,arr.length);
        //遍历该位置查看是否有key
        Node cur=arr[index];
        while (cur!=null){
            if(cur.key==key){
                //有这个key
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }
}
